package com.hdu.other.dp.statusDP;

import java.util.Arrays;

public class lc473 {
    class Solution {
        public boolean makesquare(int[] matchsticks) {
            int sum = 0;
            for (int i = 0; i < matchsticks.length; i++) {
                sum += matchsticks[i];
            }
            if (sum % 4 != 0) {
                return false;
            }
            int avg = sum / 4;
            int len = matchsticks.length;
            int status = (1 << len) - 1;
            int[] dp = new int[1 << len];
            Arrays.fill(dp, -1);
            return f(matchsticks, status, 4, avg, avg, dp);
        }

        boolean f(int[] matchsticks, int status, int k, int avg, int cur, int[] dp) {
            if (k == 0) {
                return status == 0;
            }
            if (dp[status] != -1) {
                return dp[status] == 1;
            }
            boolean ans = false;
            for (int i = 0; i < matchsticks.length; i++) {
                if ((status & (1 << i)) != 0 && cur >= matchsticks[i]) {
                    int leave = cur - matchsticks[i];
                    if (leave == 0) {
                        ans = f(matchsticks, status ^ (1 << i), k - 1, avg, avg, dp);
                    } else {
                        ans = f(matchsticks, status ^ (1 << i), k, avg, leave, dp);
                    }
                    if (ans) {
                        break;
                    }
                }
            }
            dp[status] = ans ? 1 : 0;
            return ans;
        }
    }
}
